package 二分查找;

/**
 * @Author Weton Li
 * @Date 2021/4/22 16:42
 */
public class 两数之和2_有序 {

    public static void main(String[] args) {
        int[] input = {2,7,11,13};
        int[] m = method2(input, 9);
        for (int i : m) {
            System.out.print(i+"\t");
        }
    }

    /**
     * 二分查找
     * @param arr
     * @param target
     * @return
     */
    public static int[] method(int[] arr,int target){
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int searchNum = target-arr[i];
            int start = i+1;
            int end = n-1;
            while (start <= end) { // 当start和end相同时，即代表判断当前和要查找的值（伴侣）是否相同
                int mid = (start+end)/2;
                if (searchNum<arr[mid]){
                    end = mid-1;
                }else if(searchNum>arr[mid]){
                    start = mid +1;
                }else if(searchNum==arr[mid]){
                    return new int[]{i+1,mid+1};
                }
            }
        }
        return new int[]{-1,-1};
    }

    /**
     * 双指针效率很高
     * @param arr
     * @param target
     * @return
     */
    public static int[] method2(int[] arr,int target){
        int n = arr.length;
        int left = 0;
        int right = n-1;
        while (left<right){
            if (arr[left]+arr[right] == target) {
                return new int[]{left+1,right+1};
            }else if(arr[left]+arr[right] >target){
                right--;
            }else{
                left++;
            }
        }

        return new int[]{-1,-1};
    }
}
